package com.cuz.daileetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author cuzz
 * @version 1.0
 * @description: 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 * 示例 2：
 * <p>
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 * 示例 3：
 * <p>
 * 输入：s = ""
 * 输出：0
 * <p>
 * <p>
 * 提示：
 * <p>
 * 0 <= s.length <= 3 * 104
 * s[i] 为 '(' 或 ')'
 * 通过次数191,938提交次数538,238
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 19:11 2021/10/1
 **/
public class Day13 {
    /**
     * @author cuzz
     * @description 栈
     * @date 19:32 2021/10/1
     **/
    public static class S1 {
        public static void main(String[] args) {
            System.out.println(longestValidParentheses("(()"));
        }

        public static int longestValidParentheses(String s) {
            if (s == null || s.length() <= 1) {
                return 0;
            }
            Deque<Integer> characterStack = new LinkedList<>();
            char[] strChar = s.toCharArray();
            int maxLen = 0;
            // 意味着最长括号只能从0开始
            characterStack.push(-1);
            for (int index = 0; index < strChar.length; index++) {
                if (strChar[index] == '(') {
                    characterStack.push(index);
                } else {
                    characterStack.pop();
                    if (characterStack.isEmpty()) {
                        characterStack.push(index);
                    } else {
                        maxLen = Math.max(maxLen, index - characterStack.peek());
                    }
                }
            }
            return maxLen;
        }
    }

    public static class S2 {
        public static void main(String[] args) {
            System.out.println(longestValidParentheses("(()"));
        }

        public static int longestValidParentheses(String s) {
            if (s == null || s.length() <= 1) {
                return 0;
            }
            int leftBrackets = 0;
            int rightBrackets = 0;
            int maxLen = 0;
            for (int index = 0; index < s.length(); index++) {
                if (s.charAt(index) == '(') {
                    leftBrackets++;
                } else {
                    rightBrackets++;
                }
                if (leftBrackets == rightBrackets) {
                    maxLen = Math.max(maxLen, leftBrackets * 2);
                }
                if (rightBrackets > leftBrackets) {
                    leftBrackets = 0;
                    rightBrackets = 0;
                }
            }
            leftBrackets = 0;
            rightBrackets = 0;
            for (int index = s.length() - 1; index > 0; index--) {
                if (s.charAt(index) == '(') {
                    leftBrackets++;
                } else {
                    rightBrackets++;
                }
                if (leftBrackets == rightBrackets) {
                    maxLen = Math.max(maxLen, leftBrackets * 2);
                }
                if (leftBrackets > rightBrackets) {
                    leftBrackets = 0;
                    rightBrackets = 0;
                }
            }
            return maxLen;
        }
    }
}
